//============================================================================
// Name        : Kraljice.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>

#define MAX 8

#define N 8
#define P 10000

using namespace std;

int population[P][N];

int fitnessTournament[P];

int kp[MAX];
int vr[MAX], dij45[15], dij135[15];



int random(int n) {
	return rand() % (n);
}

/* broji sa koliko se kraljica svaka sece */
int fitness(int jedinka[], int length) {
	int rezultat = 0;
	int k = 0;
	for (int i = 0; i < length; i++) {
		for (int j = i; j < length; j++) {
			if (i != j) {
				/* provera da li se dve jedinke nalaze u istoj koloni */
				if ((jedinka[i] == jedinka[j])) {
					rezultat++;
				}
				/* provera da li se seku po dijagonali od donjeg levog ugla, ka gornjem desnom */
				else if ((i + jedinka[i] == j + jedinka[j])) {
					rezultat++;
				}
				/* provera da li se seku po dijagonali od gornjeg levog ugla, ka donjem desnom */
				else if ((i - j) == (jedinka[i] - jedinka[j])) {
					rezultat++;
				}
			}
		}
	}
	return rezultat;

}

/* kao pravi crossover, uzima se p < n hromozoma od oca i n - p od majke */
void crossover(int* mom, int* dad, int* child1, int* child2) {
	int i;
	int cross = random(N);

	for (i = 0; i < cross; i++) {
		child1[i] = mom[i];
		child2[i] = dad[i];
	}
	for (; i < N; i++) {
		child1[i] = dad[i];
		child2[i] = mom[i];
	}
}

/* mutira se samo jedan gen */
void mutatiton(int individual[]) {
	int position = random(N);
	int value = random(N);
	individual[position] = value;
}

/* kreiranje jedne jedinke sa n gena */
void createIndividual(int* individual, int n) {
	for (int i = 0; i < n; i++)
		individual[i] = random(n);
}

/* kreiranje populacije od p jedinki */
void createPopulation(int p) {
	for (int i = 0; i < p; i++)
		createIndividual(population[i], N);
}

void swap(int individual1[], int individual2[]) {
	int temp;
	for (int i = 0; i < N; i++) {
		temp = individual1[i];
		individual1[i] = individual2[i];
		individual2[i] = temp;
	}
}

/* turnir u kojem bi trebalo da pobedi jedinka sa 0 preseka */
void tournament() {
	int p = P;
	int k = 0;
	int fit = fitness(population[0], N);

	while (fit > 0) {
		createPopulation(P);
		for (int i = 0; i < P; i++) {

			if (i >= 1 && i < p - 1) {
				crossover(population[i], population[i - 1], population[i],
						population[i + 1]);
				mutatiton(population[i - 1]);
				mutatiton(population[i]);
				mutatiton(population[i + 1]);
			}

			fitnessTournament[i] = fitness(population[i], N);

			if (fit >= fitnessTournament[i]) {
				fit = fitnessTournament[i];
			}

			if (fit == 0)
				// {
				//   cout << "Pobednik je : " ;
				// for(int j = 0; j < N; j++)
				//   cout << population[i][j] << " ";
				// cout << endl;
				return;
			// }

		}

	}
}

void stampaj(){
    int i, j;
    for(i = 0; i < MAX; i++){
        for(j = 0; j < MAX; j++){
            if(kp[j] == i)
                printf("1 ");
            else
                printf("0 ");
        }
        printf("\n");
    }
}

int postaviKraljice(int kn){
    int i;
    for(i = 0; i < 8; i++)
    {
        if(!vr[i] && !dij45[i + kn] && !dij135[kn - i + 7])
        {
            if(kn < 7)
            {
                kp[kn] = i;
                vr[i] = 1;
                dij45[i + kn] = 1;
                dij135[kn - i + 7] = 1;
                if(postaviKraljice(kn + 1))
                {
                    return 1;
                }
                vr[i] = 0;
                dij45[i + kn] = 0;
                dij135[kn - i + 7] = 0;
            }
            else{
                kp[kn] = i;
                stampaj();
                return 1;
            }
        }
    }
    return 0;
}

void inicijalizuj()
{
    int i, j;
    for(i = 0; i < 8; i++)
    {
        vr[i] = dij45[i] = dij135[i] = 0;
    }
    for( ; i < 15; i++)
    {
        dij45[i] = dij135[i] = 0;
    }
    if(!postaviKraljice(0))
        printf("Nema resenja \n" );
}


int main() {
	srand(time(NULL));
	for (int i = 0; i < 100; i++)
		tournament();
	//  inicijalizuj();  //za backtracking;
	return 0;
}
